// Created by WXX on 2021/12/24 20:41
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 执行用时：4 ms, 在所有 C++ 提交中击败了90.65%的用户
 * 内存消耗：9.4 MB, 在所有 C++ 提交中击败了63.70%的用户
 */
class Solution {
public:
    void duplicateZeros(vector<int> &arr) {

        int n = arr.size();
        arr.push_back(0);

        for (int i = 0, cnt = 0; i < arr.size(); i++) {
            if (arr[i]) cnt++;
            else cnt += 2;
            if (cnt >= n) {
                for (int j = cnt - 1; i >= 0; i--) {
                    if (arr[i]) arr[j--] = arr[i];
                    else {
                        arr[j--] = 0;
                        arr[j--] = 0;
                    }
                }
                break;
            }
        }

        arr.pop_back();
    }
};

void OutputBasicArray1D(vector<int> nums) {
    cout << "[";
    for (int i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ", ";
    }
    cout << "]" << endl;
}

int main() {

    vector<int> arr = {1, 0, 2, 3, 0, 4, 5, 0};
    Solution().duplicateZeros(arr);
    OutputBasicArray1D(arr);

    return 0;
}
